//198 劫匪抢房子
/*
假如你是一个劫匪，并且决定抢劫一条街上的房子，每个房子内的钱财数量各不相同。如果
你抢了两栋相邻的房子，则会触发警报机关。求在不触发机关的情况下最多可以抢劫多少钱

输入输出样例：
	输入是一个一维数组，表示每个房子的钱财数量；输出是劫匪可以最多抢劫的钱财数量

Input: [2,7,9,3,1]
Output: 12

分析：
	求最终的结果，可用动态规划
	如果抢到第i间房为最多财务，设为d[i]
	则如果抢到d[i]，其上一间抢的房子为d[i-2]，
	如果没抢到d[i]，其上一间抢的房子为d[i-1],
	最终财物d[i] = max(d[i-1]，d[i-2]+num[i-1])
*/
//方法一：递归
int rob(vector<int> &nums)
{
	if (nums.empty())
		return 0;
	int n = nums.size();
	vector<int> dp(n + 1, 0); //n+1多构造一个位置，使得数组最前面的位置为0，配合dp[i-2]使用
	dp[1] = nums[0];
	for (int i = 2; i <= n; ++i)
	{
		dp[i] = max(dp[i - 1], nums[i - 1] + dp[i - 2]);
	}
	return dp[n];
}
//方法二：空间压缩O(1)
int rob(vector<int> &nums)
{
	//
	if (nums.empty())
		return 0;
	int n = nums.size();
	if (n == 1)
		return nums[0];
	int pre2 = 0, pre1 = 0, cur;
	for (int i = 0; i < n; ++i)
	{
		cur = max(pre2 + nums[i], pre1);
		pre2 = pre1;
		pre1 = cur;
	}
	return cur;
}